package solution.design;

import java.util.List;
import java.util.PriorityQueue;

/**
 * @author zhangmin
 * @create 2022-05-20 10:52
 * 最小生成树的Prim 算法的代码实
 */
public class Prim {
    //优先队列，存储横切边
    private PriorityQueue<int[]> pq;
    //记录哪些节点已经成为最小生成树的一部分
    private boolean[] isMST;
    //记录最小生成树的权重和
    private int wSum=0;
    //用邻接链表表示图,三元组 int[]{from, to, weight} 表示一条边
    private List<int[]>[] graph;
    private Prim(List<int[]>[] graph){
        this.graph=graph;
        this.pq=new PriorityQueue<>((a,b)->{
            return a[2]-b[2];
        });
        int n=graph.length;
        this.isMST=new boolean[n];
        //随便从一个点开始切分，可以从0开始
        isMST[0]=true;

    }
    //将s的横切边加入优先队列
    void cut(int s){
        //遍历s的邻边
        for (int[] edge:graph[s]) {
            int to=edge[1];
            if (isMST[to]){
                //相邻接点 to 已经在最小生成树中，跳过，避免产生环
                continue;
            }
            pq.offer(edge);
        }
    }
    //最小生成树的权重和
    int weightSum(){
        return wSum;
    }
    boolean allConnected(){
        for (int i = 0; i < isMST.length; i++) {
            if (!isMST[i]){
                return false;
            }
        }
        return true;
    }
}
